/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._445;

import java.util.Stack;

/**
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._445
 * @ClassName: AddTwoNumbers
 * @Author: linyaonan
 * @Date: 2020/4/14 16:16
 */
public class AddTwoNumbers {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }
        ListNode p = null;
        // 进位标志
        boolean hasC = false;
        while (!s1.isEmpty() || !s2.isEmpty()) {
            int s1Value = 0;
            int s2Value = 0;
            if (!s1.isEmpty()) {
                s1Value = s1.pop();
            }
            if (!s2.isEmpty()) {
                s2Value = s2.pop();
            }
            int org = s1Value + s2Value + (hasC ? 1 : 0);
            hasC = org > 9;
            int v = org % 10;
            ListNode addNode = new ListNode(v);
            addNode.next = p;
            p = addNode;
        }
        // 表示进位操作
        if (hasC) {
            ListNode addNode = new ListNode(1);
            addNode.next = p;
            p = addNode;
        }

        return p;
    }

}
